Not applicable.
This invention is in the field of data communications, and is more specifically directed to traffic management of packet-based data communications.
In the field of digital communications, whether applied to voice, video, or data communication, various techniques have been developed for routing messages among nodes, or processors, that are connected in a network. One such approach is referred to as packet-based data communications, in which certain network nodes operate as concentrators to receive portions of messages, referred to as packets, from the sending units. These packets may be stored at the concentrator, and are then routed to a destination concentrator to which the receiving unit indicated by the packet address is coupled. The size of the packet refers to the maximum upper limit of information that can be communicated between concentrators (i.e., between the store and forward nodes), and is typically a portion of a message or file. Each packet includes header information relating to the source network address and destination network address, which permits proper routing of the message packet. Packet switching with short length packets ensures that routing paths are not unduly dominated by long individual messages, and thus reduces transmission delay in the store-and-forward nodes. Packet-based data communications technology has enabled communications to be carried out at high data rates, up to and exceeding hundreds of megabits per second.
A well-known example of a fast packet switching protocol, which combines the efficiency of packet switching with the predictability of circuit switching, is Asynchronous Transfer Mode (generally referred to as xe2x80x9cATMxe2x80x9d), in which packet lengths and organization are fixed, regardless of message length or data type (i.e., voice, data, or video). The fixed packets according to the ATM protocol are referred to as xe2x80x9ccellsxe2x80x9d, and each ATM cell is composed of fifty-three bytes, five of which are dedicated to the header and the remaining forty-eight of which serve as the payload. According to this protocol, larger packets are made up of a number of fixed-length ATM cells. The fixed-size cell format enables ATM cell switching to be implemented in hardware, as opposed to software, resulting in transmission speeds in the gigabits-per-second range. In addition, the switching of cells rather than packets permits scalable user access to the network, from a few Mbps to several Gbps, as appropriate to the application. The asynchronous nature of the transmission permits ATM cells to be used in transmitting delay-tolerant data traffic intermixed with time-sensitive traffic like voice and video over the same backbone facility. To more efficiently utilize the bandwidth for these various applications, traffic management techniques are now employed which give priority to time-sensitive traffic relative to delay-tolerant traffic.
Closed loop traffic management involves the use of feedback signals between two network nodes to govern the data rates of channels, with a goal of improving the efficiency of bandwidth utilization. This efficiency improvement is particularly necessary when communication of compressed voice and video information is involved, because of the variability in bit rate caused by compression. In this case, the feedback signals enable the network to communicate either the availability of bandwidth or the presence of congestion.
Current traffic management schemes utilize various transmission categories to assign bandwidth in ATM communications. One high priority category is Constant Bit Rate (CBR), in which the transmission is carried out at a constant rate. Two categories of Variable Bit Rate (VBR) transmission are also provided, one for real-time information and another for non-real-time information. A low priority category is Unspecified Bit Rate (UBR), in which data are transmitted by the source with no guarantee of transmission speed. In the recently-developed Available Bit Rate (ABR) service class, feedback from the network nodes, via Resource Management (RM) cells or by way of explicit congestion indications in data cells, is used by the source network node to dynamically control channel transmission rate in response to current network conditions, and within certain transmission parameters that are specified upon opening of the transmission channel (i.e., in the traffic xe2x80x9ccontractxe2x80x9d).
For the ABR class of service, the source and destination nodes agree, in the traffic contract, upon the Peak Cell Rate (PCR) and Minimum Cell Rate (MCR), thus setting the upper and lower bounds of transmission for an ABR communication. Once these bounds are established, a flow control algorithm is executed, typically at the source network node and in ATM switches, to define the desired transmission rate for each channel. As is known in the art, thousands of connections may be simultaneously open between a given pair of network nodes. As such, traffic management can be a relatively complex operation, especially in controlling ABR category communications.
At the source network node, and also at switches within the ATM network (e.g., at the edges of network domains), Segmentation and Reassembly (SAR) devices or shaper devices are used to arrange and transmit ATM cells according to the traffic contract established at the time of subscription. An often-used traffic shaping device is referred to in the art as a xe2x80x9cleaky bucketxe2x80x9d, as this device includes buffers that can rapidly fill up with cell data during bursts, but steadily xe2x80x9cleakxe2x80x9d or transmit data over the network. These leaky bucket functions effectively verify conformance of each cell with respect to its traffic xe2x80x9ccontractxe2x80x9d, ensuring that one or more channels do not dominate the bandwidth, to the exclusion of others.
The algorithm according to which such conformance is defined is referred to, for example in Traffic Management Specification, Version 4.0 (The ATM Forum, April 1996), Section 4.4.2, as the Generic Cell Rate Algorithm, or GCRA. The GCRA is required, by this specification, to be performed at each public User-to-Network Interface (UNI) as part of Usage Parameter Control (UPC) operations for Peak Cell Rate (PCR) of the Cell Loss Priority (CLP=0+1) flow; similar processing is optional in Network Parameter Control (NPC) at Network-to-Node Interfaces (NNIs), for example in the case where a downstream network domain requires traffic shaping to be performed by domains transmitting traffic thereto. UPC (and, analogously, NPC) xe2x80x9cpolicesxe2x80x9d the traffic on each ATM connection to enforce the compliance of every ATM connection to its traffic contract.
Fundamentally, the leaky bucket device is a container of xe2x80x9ctokensxe2x80x9d that are periodically added to the bucket as a measure of elapsed time, where one token is removed from the bucket for every cell that is found to be compliant. An arriving cell is found to be compliant if the token bucket is not empty upon its arrival. When used as a xe2x80x9ctraffic shaperxe2x80x9d, the GCRA operates to transmit traffic at a relatively steady rate, even if the cells are arriving in a xe2x80x9cburstyxe2x80x9d fashion. It is with respect to this shaper function that the GCRA is referred to as a xe2x80x9cleaky bucketxe2x80x9d function, as the arriving cells are effectively stored and sent along the network at a fixed rate; if too many cells arrive over a period of time, the cell xe2x80x9cbucketxe2x80x9d overflows (i.e., the token bucket is empty), in which case some cells are deemed non-conforming (as arriving at an excessively high frequency) and may be discarded.
One bit in the header of each ATM cell is the CLP (Cell Loss Priority) bit. The CLP bit permits two priorities of traffic, where lower priority, CLP(1), cells may be discarded as necessary to ensure adequate network performance for higher priority CLP(0), cells. CLP(0+1) traffic refers to the aggregate traffic, including both the lower and higher priority flows. With regard to the policing function, such as using the GCRA, if a CLP(0) cell is found to be non-conforming upon arrival, this cell may be tagged by setting its CLP bit; the tagged high priority cell may still be passed if its arrival conforms to the aggregate CLP(0+1) parameters, but will be discarded if its arrival did not conform to the aggregate parameters. In any event, a selective cell discard operation may discard all CLP(1) cells, whether transmitted at low priority or tagged due to non-conformance.
The traffic contract of a Virtual Connection (VC), or channel, may have many parts. As an example, one part of the contract may limit the proximity of successive cell arrivals by specifying a Peak Cell Rate (PCR) and a Cell Delay Variation Tolerance (CDVT). In addition, a second part of the contract may impose an average traffic intensity, while permitting some degree of burstiness, by specifying a Sustainable Cell Rate (SCR) and a Burst Tolerance (BT). Other parts of the contact may even impose restrictions on the packet stream from which the cell stream of the VC is derived.
In operation, the traffic contract of each VC specifies an Increment (I) and a Limit (L). Increment I is a measure of time that corresponds to the reciprocal of either the PCR or the SCR specified in the traffic contract of the channel. Limit L corresponds to the CDVT or the BT, and as such is a measure of the acceptable deviation from the ideal delay between successive cell arrivals, or the maximum backlog due to cells arriving at a rate greater than the SCR, as specified in the traffic contract for the channel. In the interest of clarity, the description to follow will only address the use of the GCRA to verify conformance to PCR in conjunction with the CDVT part of the contract. It is to be understood that the conventional GCRA (as well as the present invention described herein) may also be used for other traffic contract verification and traffic shaping functions.
In this regard, FIG. 1a illustrates an example of a conventional virtual scheduling algorithm for the GCRA, in which the conformance of a cell k arriving at a time ta(k) is determined, using a Theoretical Arrival Time (TAT). Theoretical Arrival Time TAT is a point in time at which a cell ought to arrive if communicated exacty at the PCR. In FIG. 1a, the GCRA operation begins with process 2, in which cell k arrives at a policer function at arrival time ta(k). For purposes of this description, the policer function is a device that performs traffic policing functions, and as such corresponds to a GCRA device or virtual scheduler; further, the policer function may be implemented at the ingress of an ATM switch. When used as a shaper, the function may be implemented in an SAR device or at the egress of an ATM switch. Time ta(k) corresponds to the value of a global timer at the time of the arrival of cell k; the global timer, as will be described below, is typically a very wide (e.g., 48 bit) counter that is incremented with each clock period, wrapping around on overflow. Decision 3 is then next performed by the policer function to determine if the arrival time ta(k) is later than (i.e., greater than) the current value of Theoretical Arrival Time TAT. If so (decision 3 is YES), cell k is necessarily conforming, as its arrival occurred at a time, after the arrival of cell kxe2x88x921 for the same channel, that was longer than that indicated by the PCR of the channel. In this case, the policer function sets the current value of Theoretical Arrival Time TAT at the actual arrival time ta(k), and passes control to process 6, in which the policer function increments the Theoretical Arrival Time TAT by Increment I, which as noted above is approximately the reciprocal of the PCR for that channel, specified in the traffic contract. The process then awaits the receipt of the next cell (k+1), in which case the process will repeat.
If, however, the actual arrival time ta(k) of cell k is at or earlier than (not greater than) Theoretical Arrival Time TAT (i.e., decision 3 is NO), decision 5 is next performed by the policer function to compare the sum of the actual arrival time ta(k) and Limit L to Theoretical Arrival Time TAT. As noted above, Limit L corresponds to the Cell Delay Variation Tolerance (CDVT), which is the maximum allowed deviation in the delay between successive cell arrivals specified in the traffic contract. As such, if the actual arrival time ta(k) is within Limit L of Theoretical Arrival Time TAT (decision 5 is NO), cell k is still deemed to be conforming and Theoretical Arrival Time TAT is updated to increment I from the actual arrival time, in process 6. However, if Theoretical Arrival Time TAT is later than actual arrival time ta(k) plus Limit L (decision 5 is YES), cell k is non-conforming, and control passes to process 8 in which cell k is tagged or discarded.
FIG. 1b illustrates another conventional GCRA, implemented by way of a continuous-state xe2x80x9cleaky bucketxe2x80x9d algorithm. In this approach, cell k arrives in process 10 at time ta(k), as before. Process 12 is then performed by the policer function, to set an auxiliary variable (Xxe2x80x2) to the difference of the current value (X) of the leaky bucket counter, less the difference between the actual arrival time ta(k) and a Last Conformance Time (LCT) at which a cell arrived for the current channel that was in conformance. In decision 13, the policer function determines if the value of auxiliary variable Xxe2x80x2 is less than zero; if so (decision 13 is YES), the delay between the arrival of cell k and Last Conformance Time LCT was less than the value X of the leaky bucket counter. Cell k is then deemed conforming, the value of auxiliary variable Xxe2x80x2 is set to zero in process 14; process 16 then updates the value of leaky bucket counter X to Increment I (Xxe2x80x2 set to zero in process 14), and sets Last Conformance Time LCT to actual arrival time ta(k), since cell k was in conformance. The policer function then waits until receipt of the next cell (k+1).
If, on the other hand, the value of auxiliary variable Xxe2x80x2 is found, in process 13, to be equal to or greater than zero (decision 13 is NO), the actual arrival time ta(k) may be so soon as to render cell k in non-conformance. As before, decision 13 is NO in the event that actual arrival time ta(k) differs from Last Conformance Time LCT by a relatively small period of time. Decision 15 then determines whether the value of auxiliary variable Xxe2x80x2 is greater than Limit L; if so (decision 15 is NO), cell k is conforming, and process 16 is then carried out by the policer function to adjust the value of leaky bucket counter X (to equal the current value of auxiliary variable Xxe2x80x2 plus Increment I) and to update Last Conformance Time LCT to the arrival time ta(k). However, if the value of auxiliary variable Xxe2x80x2 is equal to or less than Limit L, cell k is not in conformance; process 18 is then performed to tag or discard cell k, as the case may be.
Many policer functions, whether implemented at a network interface or at a switch within a network, and especially in WAN-core ATM switches, are now handling large numbers of virtual channels, in some cases numbering into the hundreds of thousands. The complexity of effecting traffic shaping increases dramatically with the number of channels being handled, and particularly when ABR communications are involved. Particularly, the memory requirements involved in effecting the GCRA greatly increase, especially with the number of bits (e.g., forty) commonly used in representing time in such devices.
It is therefore an object of the present invention to provide a traffic shaping function in which the memory requirements are greatly reduced.
It is a further object of the present invention to provide such a function that may be implemented, at low cost, in conventional switches and network interface functions.
Other objects and advantages of the present invention will be apparent to those of ordinary skill in the art having reference to the following specification together with its drawings.
The present invention may be implemented in a traffic shaping or policing function in a network switch or interface in which a storage location is provided for each virtual channel to be handled. This storage location includes a field for Increment and Limit values for the channel, and also a field storing the Theoretical Arrival Time minus the Limit for the channel and utilizing a fewer number of bits than those used to represent the global time for the switch. Because of these fewer bits, wraparound of the TAT-L field requires periodic updating of its value, and fewer bits per channel reduces the overall memory necessary for traffic policing and shaping.